//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//
// 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
//
//
//
// 示例 1：
//
//
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//
//
// 示例 2：
//
//
//输入：s = "a", t = "a"
//输出："a"
//
//
//
//
// 提示：
//
//
// 1 <= s.length, t.length <= 105
// s 和 t 由英文字母组成
//
//
//
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 双指针 字符串 Sliding Window
// 👍 1199 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {
    public static void main(String[] args) {
        Solution solution = new MinimumWindowSubstring().new Solution();
        System.out.println(solution.minWindow("a" ,"b"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {
            if (s.length()<t.length()){return "";}
            if (s.equals(t)){return s;}

            int left = 0;
            int right = 0;
            int n = s.length();
            int minLen = Integer.MAX_VALUE;
            int resLeft = 0;
            int resRight = 0;
            int tLen= t.length();
            int total = 0;

            Map<Character, Integer> map = new HashMap<>();
            for (char c : t.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            while (right < n) {
                char curRight = s.charAt(right);
                if (map.getOrDefault(curRight,-1)>0) {
                    total++;
                }
                map.put(curRight, map.getOrDefault(curRight,-1) - 1);
                //包含子串则可缩小区间
                while (total==tLen) {
                    if (minLen > right - left + 1) {
                        minLen = right - left + 1;
                        resLeft = left;
                        resRight = right;
                    }
                    char curLeft = s.charAt(left);
                    if (map.get(curLeft)==0) {
                        total--;
                    }
                    map.put(curLeft, map.get(curLeft) + 1);
                    left++;
                }
                right++;
            }

            return minLen==Integer.MAX_VALUE?"":s.substring(resLeft, resRight+1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}